#include "lru.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 函数：模拟LRU页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */
void
lru_page_replacement (char *queue_frames, int num)
{
  // TODO
  int *frames = malloc (num * sizeof (int));
  if (frames == NULL)
    {
      fprintf (stderr, "Memory allocation failed\n");
      return;
    }
  
  int *counter = malloc (num * sizeof (int));
  if (counter == NULL)
    {
      fprintf (stderr, "Memory allocation failed\n");
      return;
    }

  for(int i = 0; i < num; i++)
    {
      frames[i] = -1; // 初始化页框为-1，表示空闲
      counter[i] = 0; // 初始化计数器为0
    }
  
  int time=0; // 用于记录时间戳
  int page_faults = 0; // 页面错误计数器

  const char delimiter[] = ",";
  char *str=queue_frames;
  char *token = strtok(str, delimiter);
    
    while (token != NULL) {
        int page = atoi(token); // 将字符串转换为整数
        int found = 0; // 标志位，表示是否找到页面
        for (int i = 0; i < num; i++) {
            if (frames[i] == page) {
                found = 1; // 找到页面
                counter[i] = ++time; // 更新计数器
                break;
            }
        }
        if (!found) { // 页面未找到，发生页面错误
            page_faults++;
            int lru_index = 0; // 用于找到最久未使用的页面
            int lru_time = counter[0]; // 初始化为第一个页面的时间戳
            for(int j=1;j<num;j++)
            {
              if(counter[j]<lru_time)
              {
                lru_time=counter[j];
                lru_index=j;
              }
            }
            frames[lru_index] = page; // 替换最久未使用的页面
            counter[lru_index] = ++time; // 更新计数器
        }
        // 打印当前页框状态 
        printf("Access:%d,Frames: [", page);
        for (int i = 0; i < num; i++) {
          printf("%d", frames[i]);
          if(i<num-1)
            printf(",");
        }
        printf("]\n");
        token = strtok(NULL, delimiter); // 继续提取下一个
    }

  free(frames); // 释放分配的内存
  return;
}
